package sort;

import java.util.Arrays;
import java.util.Date;

/**
 * Created by IntelliJ IDEA.
 * User: 杰哥
 * Date: 2020/4/5
 * Time: 18:47
 */
public class ShellSort {
    public static void main(String[] args) {
        int size = 20000000;
        int arr[] = new int[size];
//        int arr[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        for (int i = 0; i < size; i++) {
            arr[i] = (int)(Math.random() * size);
        }
        Date date1 = new Date();
        shellSort2(arr);
        Date date2 = new Date();
        System.out.println("用时：" + (date2.getTime() - date1.getTime()) + "毫秒" );
//        System.out.println(Arrays.toString(arr));
    }

    /**
     * 希尔排序(交换法)
     * @param arr
     */
    public static void shellSort1(int[] arr) {
        int temp = 0;
        for (int gap = arr.length/2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if(arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] =  arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }
    }

    /**
     * 希尔排序(移位法)
     * @param arr
     */
    public static void shellSort2(int[] arr) {
        for (int gap = arr.length/2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                while (j - gap >= 0 && temp < arr[j - gap]) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
    }

    public static void testSort(int[] arr) {
        int temp = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = i -1; j >= 0; j -= 1) {
                if(arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
//            System.out.println(Arrays.toString(arr));
        }
    }
}
